package demo;

import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最强祝福力场
    public int fieldOfGreatestBlessing(int[][] forceField) {
        Set<Long> rSet = new HashSet<>();
        Set<Long> cSet = new HashSet<>();

        for (int[] q : forceField) {
            double s = ((double) q[2] / 2);
            long r1 = (long) Math.floor(2 * (q[0] - s));
            long r2 = (long) Math.ceil(2 * (q[0] + s));
            long c1 = (long) Math.floor(2 * (q[1] - s));
            long c2 = (long) Math.ceil(2 * (q[1] + s));
            rSet.add(r1);
            rSet.add(r2);
            cSet.add(c1);
            cSet.add(c2);
        }

        List<Long> rList = rSet.stream().sorted().toList();
        List<Long> cList = cSet.stream().sorted().toList();

        int[][] d = new int[rList.size() + 1][cList.size() + 1];
        for (int[] q : forceField) {
            double s = ((double) q[2] / 2);
            int r1 = index(rList, (long) Math.floor(2 * (q[0] - s)));
            int r2 = index(rList, (long) Math.ceil(2 * (q[0] + s)));
            int c1 = index(cList, (long) Math.floor(2 * (q[1] - s)));
            int c2 = index(cList, (long) Math.ceil(2 * (q[1] + s)));

            d[r1][c1]++;
            if (c2 + 1 < d[0].length)
                d[r1][c2 + 1]--;
            if (r2 + 1 < d.length)
                d[r2 + 1][c1]--;
            if (r2 + 1 < d.length && c2 + 1 < d[0].length)
                d[r2 + 1][c2 + 1]++;
        }

        int max = 0;
        for (int i = 0; i < rList.size(); i++) {
            for (int j = 0; j < cList.size(); j++) {
                if (i > 0)
                    d[i][j] += d[i - 1][j];
                if (j > 0)
                    d[i][j] += d[i][j - 1];
                if (i > 0 && j > 0)
                    d[i][j] -= d[i - 1][j - 1];
                max = Math.max(max, d[i][j]);
            }
        }

        return max;
    }


    private int index(List<Long> list, long value) {
        return Collections.binarySearch(list, value);
    }
}
